home *** CD-ROM | disk | FTP | other *** search
/ Amiga Collections: Bavarian / Bavarian #197 (19xx)(APS Electronic).zip / Bavarian #197 (19xx)(APS Electronic).adf / prg.doc < prev    next >
Text File  |  1988-06-01  |  11KB  |  229 lines
  1.  
  2. AmigaLisp - Programmdokumentation
  3. ---------------------------------
  4.  
  5.  
  6. Die grundlegenden Datenstrukturen :
  7.  
  8. Alle Lisp-Daten werden auf dem Heap angelegt. Dazu gibt es einige
  9. Verkettungsstrukturen. Zur Identifizierung erhält jede Struktur eine
  10. Typkennung, die sich stets in der Komponente knotentyp wiederfindet.
  11.  
  12. atom - nimmt alle Lisp-Atome als Zeichenkette auf. Zahlen werden jedoch
  13. verschlüsselt : zeichenkette[0]=='æ' dient als Kennung und zeichenkette[1]
  14. kann die Werte 'B' für Bruch- oder 'F' für Fließkommazahl enthalten.
  15. Um mit Zahlknoten leichter arbeiten zu können, gibt es für Brüche die
  16. Struktur bruch und für fließkommazahlen die Struktur dezimal. Beide sind
  17. aber Spezielfälle von atom. Wahrheitswerte werden nicht mit Knoten festge-
  18. halten. NIL wird durch einen Nullzeiger und t (TRUE) durch den Zeiger
  19. "wahr" dargestellt. Zu jeder Primitive existiert ein fest angelegter Knoten,
  20. so daß auch hier nur Zeiger verwaltet werden müssen.
  21. Atome erhalten die Typkennung 2.
  22.  
  23. paar - ist ein Punktepaar-Knoten, d.h. ein Paar von Zeigern auf weitere
  24. Strukturen vom Typ paar oder auf Atom-Knoten. Mit dieser Struktur werden
  25. Listen und Bäume verkettet. Typkennung : 1
  26.  
  27. varlist - ist ein Knoten zum Aufbau eines binären Variablenbaums. (siehe
  28. Variablenverwaltung) Folglich existieren Zeiger auf den rechten/linken
  29. Teilbaum. Ein weiterer Zeiger weist auf einen atomaren Knoten, der den
  30. Namen der Variable aufnimmt. Der letzte Zeiger bezeichnet den Eintrag des
  31. Symbols. Da lokale Variablen die gleichen Namen wie globale tragen dürfen,
  32. kann ein Symbol mehrfach belegt sein. Daher werden die verschiedenen Werte
  33. in einer stackähnlichen Liste verwaltet. Die Wurzel des Variablenbaums ist
  34. symbolliste. Typkennung : 3
  35.  
  36. objekt - Das Vektorgrafikmodul ermöglicht die Einrichtung von
  37. Grafikobjekten. Diese Struktur verwaltet ein solches Objekt. Alle Objekte
  38. sind in einer Liste zusammengefaßt, deren Kopfzeiger objektliste ist.
  39. Typkennung : 5
  40.  
  41. Die Funktionen :
  42.  
  43. Modul1
  44.  
  45. Zur Speicherverwaltung
  46.  
  47. Vom System wird ein 32K-großer Bereich angefordert, der nun selbstständig
  48. verwaltet wird. Dazu werden Marken eingeführt: Zu Beginn jedes Eintrags im
  49. Bereich steht ein Zeiger, der auf den nächsten Eintrag bzw. auf den
  50. nächsten Freiraum weist. Diese Zeiger weisen nur auf gerade Adressen. So
  51. kann das untere Bit als Kennung benutzt werden, ob das nachfolgende Segment
  52. frei oder mit Daten belegt ist (gesetzt = belegt). Das Ende des
  53. selbstverwalteten Speichers wird durch den Zeiger 0xfffffffe markiert.
  54. Reicht der angeforderte Speicher nicht aus, so wird ein weiterer 32K-Block
  55. initialisiert. Zur Verkettung dieser Blöcke wird die Adresse des neuen
  56. Blocks mit 0x80000001 AND-verknüpft und an die Stelle des alten 0xfffffffe-
  57. Zeigers gesetzt. Das Feld segmente verwaltet die 32K-Blöcke.
  58. Die Befehle new und dispose können wie in Turbo-Pascal benutzt werden.
  59. Für die Pufferung von Ein- und Ausgaben werden zusätzlich ebenfalls jeweils
  60. 32K reserviert.
  61. Da bei der Abarbeitung eines Lisp-Programms sehr viele unterschiedlich Große
  62. Knoten anfallen, muß eine Garbage-Collection implementiert sein. Diese
  63. gliedert sich in zwei Teile : Tritt ein akuter Speichermangel auf, so werden
  64. zunächst benachbarte freie Speichereinheiten zusammengefaßt. (Funktion
  65. angliedern) Gelengt der Interpreter auf die 0-te Rekursionsebene, so kann
  66. eine komplette Garbage-Collection durchgeführt werden. Dabei werden alle
  67. unnützen Freiräume in den 32K-Segmenten durch Umkopieren behoben. Die
  68. Referenzen der verschobenen Daten werden in allen Knoten geändert.
  69.  
  70. Ein-/Ausgabe von Listen
  71.  
  72. Mit den Funktionen output und input können Listen ein- und ausgegeben
  73. werden. Sie stützen sich auf listout, leerweg, atomin und listin ab.
  74. Die Ausgabe kann in eine Datei, auf den Drucker und auf den Bildschirm
  75. gelangen. datprint sorgt für den richtigen Datenfluß.
  76. Die Prozedur edit ruft Funktionen zur Eingabe von der Tastatur auf.
  77.  
  78.  
  79. Modul2
  80.  
  81. Variablenverwaltung
  82.  
  83. Die Funktionen suchsymbol, searchsymbol, initsymbol und delsymbol lesen,
  84. schreiben oder ändern im Variablenbaum. rekaus und vlist geben alle
  85. gespeicherten Symbolnamen aus.
  86.  
  87. ALisp-Primitive
  88.  
  89. Die Namen der Lisp-Befehle werden in initbefehl festgelegt. Hier werden sie
  90. auch alphabetisch sortiert, damit spätere Suchen binär und damit schneller
  91. geschehen können. Die Anzahl der Befehle muß im Macro anzahl festgelegt
  92. sein. Dieses findet sich sowohl in Modul2 als auch in Modul1. Die Anzahl muß
  93. stimmen! Die Funktion befehl prüft, ob ein Befehl vorliegt.
  94.  
  95. Auswertung von Lisp-Ausdrücken
  96.  
  97. evaluate ist die Kernprozedur des Interpreters. Hier wird geprüft, ob ein
  98. Atom oder ob eine Liste ausgewertet werden soll. Bei Atomen werden als Ergeb-
  99. nis der Auswertung diese ohne Veränderung wieder zurückgegeben. Nur Symbole
  100. bilden eine Ausnahme : Hier wird ihr Wert mitgeteilt, bei Primitiven deren
  101. Nummern. Soll eine Liste ausgewertet werden, so muß das erste Listenelement
  102. zu einem Lambda- oder Macro- Term auswerten oder aber eine Primitive sein.
  103. Die zu den Primitiven gehörenden Bearbeitungsprozeduren werden nun über eine
  104. Sprungtabelle erreicht.
  105.  
  106. main ist das Hauptprogramm. Hier werden Parameter beim Aufruf des
  107. Interpreters gelesen und hier liegt auch die Eingabe-Auswertung-Ausgabe -
  108. Schleife, die das Grundprinzip von Lisp-Interpretern ist.
  109.  
  110. Modul3
  111.  
  112. Zunächst findet sich hier eine Tabelle aller Fehlermeldungen. Dann folgt die
  113. Funktion genug_parameter, die überprüft, ob eine Lisp-Primitive genug
  114. Parameter erhält. Danach folgen die grundlegenden Primitiven. Ihre
  115. Implementation ist für sich betrachtet jeweils leicht zu durchschauen.
  116. Deshalb möchte ich hier nur den prinzipiellen Aufbau eines Befehls
  117. besprechen.
  118. Soll ein neuer Befehl hinzugefügt werden, so müssen die beiden anzahl-Macros
  119. um 1 erhöht werden. In Modul2 wird die Realisierungsprozedur als extern
  120. gekennzeichnet. Der Name des neuen Befehls wird an die Tabelle in initbefehl
  121. gehängt und der Aufruf der Prozedur wird an das Ende der Sprungtabelle in
  122. evaluate geschrieben. evaluate übergibt nun einen Zeiger auf die Liste aller
  123. Parameter, die mit atom und paar aufgebaut ist. Bei der Abarbeitung dieser
  124. Liste muß dafür gesorgt werden, daß keine hängenden Zeiger entstehen, d.h.
  125. wenn die Listenelemente nicht zu neuen Strukturen verarbeitet werden,
  126. sollten sie gelöscht werden. Jede Befehlsfunktion muß einen Zeiger auf ein
  127. Atom oder auf eine Liste zurückgeben. Soll eine Primitive ohne Rückgabewert
  128. definiert werden, so ist der Zeiger leeres_atom zurückzugeben.
  129.  
  130. ---------Beispiel der Implementierung einer Befehlsfunktion:-----------
  131.  
  132. struct atom *XY(parameter)
  133. struct paar *parameter;
  134. {  if(genug_parameter(parameter,2,3))
  135.    {  struct atom *hilf;
  136.       struct paar *merke;
  137.       hilf=evaluate(parameter->CAR);
  138.       merke=parameter;parameter=parameter->CDR;dispose(merke);
  139.       [...]
  140.       return(leeres_atom);
  141.    }
  142.    else
  143.    {  delete(parameter);
  144.       return(-1L);
  145.    }
  146. }
  147.  
  148. -----------------------------------------------------------------------
  149.  
  150. Die Primitive erwartet mindestens zwei und höchstens 3 Parameter. Ist diese
  151. Voraussetzung nicht erfüllt, so wird die Parameterliste gelöscht. Dazu dient
  152. delete, delete löscht stets einen kompletten Lisp-Baum - dispose hingegen
  153. löscht genau einen Knoten. Ein Zeiger mit dem Wert -1L weist immer auf einen
  154. Fehler hin.
  155. Stimmen die Voraussetzungen, so wird der erste Parameter ausgewertet, und
  156. anschließend wird die Parameterliste entsprechend verkürzt.
  157.  
  158. In Modul3 werden auch Zahlenformate umgewandelt. Mit den Befehlen getfloat
  159. und getint können aus Zahlknoten Ganzzahl- oder Fließkommazahlen gelesen
  160. werden. Weiterhin ist hier die Bruchrechnung implementiert.
  161.  
  162. Modul4
  163.  
  164. Hier finden sich die Lisp-Kontrollstrukturen. Die zugehörigen Funktionen
  165. sind aufgebaut wie Befehlsfunktionen. Die Umsetzung wird leicht
  166. verständlich, wenn man die Definition dieser Programmelemente in ALisp.doc
  167. berücksichtigt. Noch eine Bemerkung zu den Schleifen : Bei jedem
  168. Schleifendurchlauf wird eine Kopie des Schleifenrumpfes erstellt, die dann
  169. abgearbeitet wird. Dadurch benötigen Schleifen etwa ebensoviel Speicherplatz
  170. wie die entsprechenden rekursiven Lösungen.
  171.  
  172. Modul5
  173.  
  174. Die Stringbefehle sind denen von Basic und XLisp nachempfunden.
  175.  
  176. Modul6 und Modul7
  177.  
  178. In diesen Moduln sind alle Grafikbefehle definiert. Wird der Grafikmodus
  179. eingeschaltet, so erscheint ein neues Fenster. Dazu wird aber im Hintergrund
  180. noch ein Screen geöffnet, der als Puffer für den Fill-Befehl sowie als
  181. Zwischenspeicher für Vektorgrafikfilme dient.
  182. Interessant ist vornehmlich Modul7:
  183.  
  184. Die Grafikobjekte bestehen aus einer Liste von Polygonzügen, Punkten und
  185. Strecken. Ein Grafikobjekt wird mit defobj angelegt. Dabei wird die
  186. übergebene Baumstruktur in ein Feld dynamischer Länge übersetzt, das Teil
  187. der Struktur objekt ist. Auf die Grafikobjekte können lineare Abbildungen
  188. zur Rotation und Streckung sowie eine Abbildung zur Translation angewendet
  189. werden. Diese Abbildungen werden durch Matrizen ausgedrückt, die in
  190. initmatrix vordefiniert sind. Hintereinanderausführung von Abbildung
  191. bedeutet nun Multiplikation der entsprechenden Matrizen. So werden bei den
  192. entsprechenden Befehlen nur Steuersequenzen auf den Stack "operationen" des
  193. Grafikobjekts gelegt. Erst wenn es dargestellt werden muß, werden die zu den
  194. Sequenzen gehörenden Matrizen erstellt, verknüpft und dann auf die einzelnen
  195. Punkte der Polygonzüge angewendet. Die Funktionen zusammenfassen, vemult und
  196. polymult sowie plotten beschreiben diese Tätigkeiten.
  197. Linien, die den Fensterrand überschreiten, müssen entsprechend abgeschnitten
  198. werden. Dafür sorgt in der Prozedur linie der Cohen-Sutherland-Clipping-
  199. Algorithmus. Die Grafik wird durch das Fenster des Moitors betrachtet. Die
  200. Konstante zoom gibt die Entfernung des Beobachters zum Bildschirm an.
  201. Linien, die durch das Bildschirmfenster ragen, werden in polymult ebenfalls
  202. gekürzt. 
  203. Die Liste der Grafikobjekte kann mit objlist ausgegeben werden.
  204. Ein HiddenLine-Algorithmus ist bereits eingebaut, wird aber noch nicht
  205. benutzt, da bisher keine ausgefüllten Flächen gezeichnet werden können.
  206. Die Funktion ma_aus dient nur dazu, Matrizen zu Wartungszwecken auszugeben.
  207.  
  208. Modul8
  209.  
  210. Die Benutzerschnittstelle macht Gebrauch von den vielfältigen Möglichkeiten
  211. des Amiga-Betriebssystems. Soll ALisp auf andere Rechner portiert werden, so
  212. wird sich hier die Hauptarbeit ergeben :
  213. Zunächst werden die Pulldownmenüs definiert, anschließend die beiden Fenster
  214. und Mauszeiger. nprint gibt Texte im Dialogfenster aus, rprint stellt sie
  215. zusätzlich noch in einer Warnfarbe dar. req liest einen Filenamen über einen
  216. Requester ein. doscommand öffnet ein neues CLI-Fenster. coninit bindet die
  217. Benutzeroberfläche ins System ein. menu fragt die Menüs ab, transform
  218. wandelt RAWKEY-Codes in Ascii-Daten um. cursorcontrol steuert den Cursor im
  219. Eingabefenster, escape prüft den Menüpunkt "Evaluierung abbrechen" und
  220. newcon liest schließlich aus dem Eingabefenster einen Text ein und verbindet
  221. die anderen Interaktionsmöglichkeiten. conreinit schließt die
  222. Benutzeroberfläche.
  223.  
  224. Zur Compilierung :
  225.  
  226. Das Programm erwartet Integer-Zahlen der Länge 4 Bytes. Bei vielen
  227. Zeigerzuweisungen treten Typkonflikte auf, die aber vom C-Compiler korrekt
  228. behandelt werden. Die Mathe - Library m.lib muß hinzugelinkt werden.
  229.